A standard technique from the hashing literature is to use two hash functions h1(x)
and h2(x)to simulate additional hash functions of the form gi(x) = h1(x)+ih2(x). We demonstrate
that this technique can be usefully applied to Bloom filters and related data structures. Specifically,
only two hash functions are necessary to effectively implement a Bloom filter without any loss in
the asymptotic false positive probability. This leads to less computation and potentially less need for
randomness in practice.
and h2(x)to simulate additional hash functions of the form gi(x) = h1(x)+ih2(x). We demonstrate
that this technique can be usefully applied to Bloom filters and related data structures. Specifically,
only two hash functions are necessary to effectively implement a Bloom filter without any loss in
the asymptotic false positive probability. This leads to less computation and potentially less need for
randomness in practice.
